|
A summed area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid. In the image processing domain, it is also known as an integral image. It was first introduced to computer graphics in 1984 by Frank Crow for use with mipmaps. In computer vision it was first prominently used within the Viola–Jones object detection framework in 2001. However, historically, this principle is very well known in the study of multi-dimensional probability distribution functions, namely in computing 2D (or ND) probabilities (area under the probability distribution) from the respective cumulative distribution functions.〔 〕 ==The algorithm== As the name suggests, the value at any point (''x'', ''y'') in the summed area table is just the sum of all the pixels above and to the left of (''x'', ''y''), inclusive:〔 〕〔 〕 : Moreover, the summed area table can be computed efficiently in a single pass over the image, using the fact that the value in the summed area table at (''x'', ''y'') is just: : Once the summed area table has been computed, the task of evaluating the intensities over any rectangular area requires only four array references. This allows for a constant calculation time that is independent of the size of the rectangular area. That is, using the notation in the figure at right, having A=(x0, y0), B=(x1, y0), C=(x0, y1) and D=(x1, y1), the sum of i(x,y) over the rectangle spanned by A, B,C and D is: : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Summed area table」の詳細全文を読む スポンサード リンク
|